#include "../include/tree.h"

inline bool tree_is_empty(const tree_t * head) {
	if (head->first_son == NULL) {
		return true;
	}
	return false;
}

inline bool tree_is_exist(const tree_t * head, const tree_t * unit) {
	if (head == unit->head) {
		return true;
	}
	return false;
}

inline void tree_empty(tree_t * head) {
	head->first_son = NULL;
}

inline bool tree_is_head(tree_t * entry) {
	if (entry->head == entry) {
		return true;
	}
	return false;
}

inline bool tree_is_root(tree_t * entry) {
	tree_t * head = entry->head;
	if (head == NULL) {
		return false;
	}
	else if (head->first_son == entry) {
		return true;
	}	
	return false;
}

inline void tree_add_son(tree_t * entry, tree_t * unit) {
	/* 防止出现两个root节点，只允许一个root节点 */
	if (tree_is_head(entry) && !tree_is_empty(entry)) {
		return ;
	}
	/* 已经在head的管理树中*/
	if (entry->head == unit->head) {
		return;
	}
	unit->head = entry->head;	
	unit->father = entry;
	unit->first_son = NULL;
	if (entry->first_son == NULL) {
		unit->brother_left = unit;
		unit->brother_right = unit;	
	}	
	else {
		unit->brother_left = entry->first_son->brother_left;
		unit->brother_right = entry->first_son;
		entry->first_son->brother_left->brother_right = unit;
		entry->first_son->brother_left = unit;	
	}	
	entry->first_son = unit;
}

inline void __change_sons_father(tree_t * src_f , tree_t * des_f) {
	tree_t * pson = src_f->first_son;
	if (pson != NULL) {
		pson = pson->brother_right;
		while ( pson != src_f->first_son) {
			pson->father = des_f;
			pson = pson->brother_right;
		}
		pson->father = des_f;
	}
}
inline void __tree_del_son(tree_t * father, tree_t * son) {
	tree_t * p;
	/* 删除第一个孩子节点 */	
	if (father->first_son == son) {
		/* 只有一个孩子节点 */
		if (son->brother_left == son && son->brother_right == son) {
			father->first_son = son->first_son;
			if (son->first_son != NULL) {
				__change_sons_father(son, father); /* son的所有子节点的父节点都变为father */
			}
			return;
		}
		else { /*有多个孩子节点*/
			if (son->first_son == NULL) { /* 删除的节点无子节点 */
				son->brother_right->brother_left = son->brother_left;
				son->brother_left->brother_right = son->brother_right;	
				father->first_son = son->brother_right;
				son->brother_right->first_son = son->first_son;
			}
			else { /* 删除的节点有子节点,则子节点都提升到与其兄弟节点一个层次, 即将两个循环链合并 */
				father->first_son = son->first_son;
				__change_sons_father(son, father);
						
				son->first_son->brother_left->brother_right = son->brother_right;		
				son->brother_right->brother_left = son->first_son->brother_left;	
				son->first_son->brother_left = son->brother_left;
				son->brother_left->brother_right = son->first_son;
				
			}
		}
	}
	else { /*删除的孩子节点不是第一个孩子节点，这也意味着不可能只有一个孩子节点*/
		if (son->first_son == NULL) { /* 删除的节点无子节点 */
			son->brother_right->brother_left = son->brother_left;	
			son->brother_left->brother_right = son->brother_right;
		}
		else { /* 删除的节点有子节点,则子节点都提升到与其兄弟节点一个层次, 即将两个循环链合并 */
			__change_sons_father(son ,father);	
			
			son->first_son->brother_left->brother_right = son->brother_right;
			son->brother_right->brother_left = son->first_son->brother_left;
			son->first_son->brother_left = son->brother_left;
			son->brother_left->brother_right = son->first_son;
		}
	}	
}
inline void tree_del_son(tree_t * unit) {
	/*不删除head管理器*/
	if (tree_is_head(unit)) {
		return;
	}

	__tree_del_son(unit->father, unit);
	unit->head = NULL;
}
inline void __tree_del_son_all(tree_t * father, tree_t *son) {
	/* 删除第一个孩子节点 */	
	if (father->first_son == son) {
		/* 只有一个孩子节点 */
		if (son->brother_left == son && son->brother_right == son) {
			father->first_son = NULL;
			return;
		}
		else { /*有多个孩子节点*/
			son->brother_right->brother_left = son->brother_left;
			son->brother_left->brother_right = son->brother_right;	
			father->first_son = son->brother_right;
		}
	}
	else { /*删除的孩子节点不是第一个孩子节点，这也意味着不可能只有一个孩子节点*/
		son->brother_right->brother_left = son->brother_left;	
		son->brother_left->brother_right = son->brother_right;
	}	
}

inline void tree_del_son_all(tree_t * unit) {
	/*不删除head管理器*/
	if (tree_is_head(unit)) {
		return;
	}
	__tree_del_son_all(unit->father, unit);
	unit->head = NULL;
}

inline tree_t * tree_get_son(tree_t * entry, unsigned long index) {
	tree_t * pson = entry->first_son;			
	
	if (NULL == pson || index == 0) {
		return pson;
	}		
	pson = pson->brother_right;

	while (pson != entry->first_son && --index != 0) {
		pson = pson->brother_right;	
	}
	if (pson == entry->first_son) {
		return NULL;
	}
	return pson;
}

inline tree_t * tree_get_father(tree_t * unit) {
	return unit->father;
}

inline tree_t * tree_get_head(tree_t * unit) {
	return unit->head;
}

inline tree_t * tree_get_root(tree_t * unit) {
	return tree_get_head(unit)->first_son;	
}

